/*
 *三向快速排序
 */

#include<iostream>
#include<vector>

using namespace std;

void quick_sort(vector<int> &nums,int lo,int hi)
{
    if(lo>=hi)
        return;
    int lt=lo,i=lo+1,gt=hi,v=nums[lo];
    while(i<=gt)
    {
        if(nums[i]<v)
        {
            swap(nums[i],nums[lt]);
            ++i;
            ++lt;
        }else if(nums[i]>v){
            swap(nums[i],nums[gt]);
            --gt;
        }else
        {
            ++i;
        }   
    }
    quick_sort(nums,lo,lt-1);
    quick_sort(nums,gt+1,hi);
}

int main()
{
    vector<int> nums={1,2,15,0,5,34};
    quick_sort(nums,0,5); 
    for(auto num:nums)
    {
        cout<<num<<" ";
    }
    return 0;
}